<!-- This comment will put IE 6, 7 and 8 in quirks mode -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>Network BFS: Página principal</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javaScript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body onload='searchBox.OnSelectItem(0);'>
<!-- Generado por Doxygen 1.6.1 -->
<script type="text/javascript"><!--
var searchBox = new SearchBox("searchBox", "search",false,'Buscar');
--></script>
<div class="navigation" id="top">
  <div class="tabs">
    <ul>
      <li class="current"><a href="index.html"><span>Página&nbsp;principal</span></a></li>
      <li><a href="annotated.html"><span>Clases</span></a></li>
      <li><a href="files.html"><span>Archivos</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <img id="MSearchSelect" src="search/search.png"
             onmouseover="return searchBox.OnSearchSelectShow()"
             onmouseout="return searchBox.OnSearchSelectHide()"
             alt=""/>
        <input type="text" id="MSearchField" value="Buscar" accesskey="S"
             onfocus="searchBox.OnSearchFieldFocus(true)" 
             onblur="searchBox.OnSearchFieldFocus(false)" 
             onkeyup="searchBox.OnSearchFieldChange(event)"/>
        <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
        </div>
      </li>
    </ul>
  </div>
</div>
<div class="contents">
<h1>Network BFS Documentación</h1></div>
<h2>------------------------------------</h2></div>
<h2>Proyecto Matematica Discreta 2 2011</h2></div>
<h2>Parte 1</h2></div>
<h2>------------------------------------</h2></div>
<h2>Integrantes:</h2></div>
<h2>-  Gallo Javier</h2></div>
<h2>-  Hubmann Lionel</h2></div>
<h2>-  Hubmann Patricio</h2></div>
<h2>-  Trossero Yanina</h2></div>
<h2>------------------------------------</h2></div>
<h2>Consideraciones de diseño</h2></div>
<pre>
- Estructura del network:
    El Network esta implementado como una tabla de nodos. Cada nodo tiene
    una lista de vecinos, en la cual también se indica la capacidad de la
    arista que va desde el nodo hasta ese vecino.
    Esta decisión fue tomada para ahorrar memoria y poder procesar grafos más
    grandes, que con otras implementaciones (por ejemplo una matriz) sería
    imposible procesar.

- Uso de Tabla Hash(GHash):
    La tabla de nodos se implementa como una tabla hash, lo que permite una muy
    buena eficiencia a la hora de obtener un vértice dado su nombre. Además nos
    permite que haya un buen uso de la memoria, dado que no se usan los nombres
    como índices de una matriz, lo que haría que el tamaño sea proporcional al
    número de vértice más grande.

- Uso de Glist para implementar tanto listas como colas:
    Aprovechando el hecho de que ya estábamos utilizando GList para implementar
    el Network y debido a las complicaciones de agregar cada módulo de GLib
    (ver 'GLib y su inclusión'), decidimos implementar el tipo 'cola' usando
    Glist, ya que ésta se comporta como una cola si usamos la función
    'g_list_append' para agregar elementos a la cola.

- Modularización de Network y BFS:
    Si bien Network y BFS son dos módulos separados, podemos observar que BFS
    modifica los nodos del Network. Esto es así porque BFS y Network están
    trabajando como si fueran un único módulo. La separación en distintos
    archivos está dada simplemente por el hecho de repartir tareas entre
    integrantes del grupo, no como una cuestión de separación entre ellos.

- Evitar Horrores de Programación:
    -Uso de 'assert' para control de precondiciones y postcondiciones.
    -Inicialización de variables luego de ser declaradas para evitar errores
    que podrían ser difíciles de detectar más adelante.
    -Nombres de variables y de funciones acordes al uso que se les da.
    -Coding Style para una mejor lectura y comprensión del código, con una gran
    cantidad de comentarios.
    -Punteros controlados antes de ser usados y asignados a NULL cuando ya no
    son necesarios para evitar posibles referencias erróneas.
    -Uso de constantes para almacenar valores críticos del programa.
    -Uso de la herramienta 'Valgrind' para detectar fugas de memoria.

- Glist como valor de retorno en Network:
    La función 'network_getNeighbors' devuelve un puntero hacia una GList, lo
    cual muestra como está implementada parte del network. Esta decisión tiene
    una doble explicación: Una de ellas es la explicación dada en 'Modulariza-
    ción de Network y BFS', la otra explicación es que devolviendo directamente
    la lista de vecinos del nodo evitamos copiar esa lista en memoria, cuyo
    tamaño puede llegar a ser bastante grande.

- Nombres de Métodos:
    Decidimos escribir los métodos con la siguiente sintaxis:
      nombremodulo_nombreMetodoEstiloJava
    esto es para dejar en claro a que módulo pertenece cada método.

- Guardar key de GLib con node_getAddress:
    La implementación de tabla hash de GLib no guarda memoria para el objeto a
    alojar, dado que el key es el número que representa al vértice, entonces al
    llamar al método de inserción de GHash usamos como key el unsigned int que
    alojamos en memoria junto con el vértice, para no tener que asignar memoria
    extra para este número. El problema es que GHash requiere un puntero a lo
    que deseamos guardar como key, y obtener la dirección de lo que retorna un
    método no esta permitido (por el compilador), por lo que creamos la función
    'node_getAddress' que retorna la dirección del unsigned int 'label' que
    necesitamos, para pasarla como parámetro a 'g_hash_table_insert'.

- Iteración en la lista de vecinos en BFS:
    Debido a que en un while se recorre la lista de vecinos, usamos el método
    next para recorrer la estructura e ir usando cada vértice, pero debido a
    unos problemas con respecto al uso de este método, tuvimos que cambiar a un
    'for' donde se usa un contador 'i' junto con la función 'g_list_nth' para
    recorrer la lista.

- GLib y su inclusión:
    Después de buscar diferentes implementaciones de estructuras de datos,
    elegimos usar GLib por algunas razones:
        -GLib incluye todas las estructuras requeridas por el programa.
        -GHash es una implementación con resize automático que no esta basada
         en keys de tipo string, los cuales consumen mucha memoria extra, y
         brindando además una función de hash adecuada para int.
        -GList es una implementación de listas doblemente enlazadas que puede
         usarse también como cola o pila, limitando los métodos usados.
        -Ya estábamos familiarizados con su uso.
    Debido a la cantidad de problemas relacionados con la poca portabilidad del
    manejo de memoria, las dificultades de compilar el código de la librería y
    después de muchos intentos de incluirla sin éxito, decidimos tomar los
    módulos mínimos y necesarios para ghash.c y glist.c, y modificar un poco su
    implementación, recortando las dependencias y realizando el manejo de
    memoria a través de malloc y free, en vez de las funciones de GLib creadas
    para tal propósito, lo que permitió tener en 100KB las dos estructuras y
    con código totalmente portable.

- Diseño de BFS:
    La implemetación del algoritmo utilizada no es la provista por la cátedra
    sino que se hizo una readaptación del BFS original. El algoritmo del BFS
    "puro" se busco vía web, para más detalles ver la documentación de 'bfs.c'
    donde tal algoritmo está comentado. La decisión de usar esta implementación
    y no la dada por la cátedra viene de que era más fácil de programar según
    nuestras estructuras de datos ya definidas.

</pre>
<!--- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&nbsp;</span>Todo</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&nbsp;</span>Clases</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&nbsp;</span>Archivos</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&nbsp;</span>Funciones</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<hr size="1"/><address style="text-align: right;"><small>Generado el Wed Apr 13 17:47:44 2011 para Network BFS por&nbsp;
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
</body>
</html>
